package PriorQueue;

public class TextHeap {
    public int[] elem;
    public int usedSize;

    public TextHeap() {
        this.elem = new int[10];
    }
    public void initElem(int[] array) {//初始化堆
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }
    public void createHeap() {
        for (int parent = (usedSize-1-1)/2; parent >=0; parent--) {
            shiftDown(parent,usedSize);
        }
    }
    /*
    * 父亲下标
    * 每棵树的结束的下标*/
    public void shiftDown(int parent,int len) {//向下调整：是相对于父亲节点来说的，每一个节点都要从父亲节点往下走
        int child = parent*2 + 1;
        while (child < len) {//最起码要有左孩子
            if (child+1 < len && elem[child] < elem[child+1]) {
                child++;//上面的条件是要保证一定要右孩子，才能让child++，否则数组就越界了
            }
            //child下标  一定是最大孩子的下标
            if (elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;
                child = 2*parent + 1;
            }else {
                break;
            }
        }
    }
    public boolean isFull() {
        return usedSize == elem.length;
    }
    //删除大堆中的根节点
    public void pop() {
        if (isEmpty()) {
            return;
        }
        int len = usedSize - 1;
        int parent = 0;
        //1.交换完全二叉树的根节点和最后一个节点
        int tmp = elem[parent];
        elem[parent] = elem[len];
        elem[len] = tmp;
        usedSize--;
        //进行向下调整
        shiftDown(parent,len);
    }
    public boolean isEmpty() {
        return usedSize == 0;
    }
//堆排序
    //时间复杂度：O（n*logn）
    //空间复杂度：O（1）
    public void heapSort() {
        int end = usedSize - 1;
        while (end > 0) {
            int tmp = elem[0];
            elem[0] = elem[end];
            elem[end] = tmp;
            shiftDown(0,end);
            end--;
        }
    }
}
